Reliable communication is a fundamental primitive in distributed systems prone to Byzantine (i.e. arbitrary, and possibly malicious) failures to guarantee integrity, delivery and authorship of messages exchanged between processes. Its practical adoption strongly depends on the system assumptions. One of the most general (and hence versatile) such hypothesis assumes a set of processes interconnected through an unknown communication network of reliable and authenticated links, and an upper bound on the number of Byzantine faulty processes that may be present in the system, known to all participants. To this date, implementing a reliable communication service in such an environment may be expensive, both in terms of message complexity and computational complexity, unless the topology of the network is known. The target of this work is to combine the Byzantine fault-tolerant topology reconstruction with a reliable communication primitive, aiming to boost the efficiency of the reliable communication service component after an initial (expensive) phase where the topology is partially reconstructed. We characterize the sets of assumptions that make our objective achievable, and we propose a solution that, after an initialization phase, guarantees reliable communication with optimal message complexity and optimal delivery complexity.

Boosting the efficiency of Byzantine-tolerant reliable communication / Bonomi, Silvia; Farina, Giovanni; Tixeuil, Sébastien. - 12514:(2020), pp. 29-44. (Intervento presentato al convegno Symposium on Stabilization, Safety, and Security of Distributed Systems tenutosi a Austin, TX, USA) [10.1007/978-3-030-64348-5_3].

Boosting the efficiency of Byzantine-tolerant reliable communication

Bonomi, Silvia;Farina, Giovanni
;
Tixeuil, Sébastien
2020

Abstract

Reliable communication is a fundamental primitive in distributed systems prone to Byzantine (i.e. arbitrary, and possibly malicious) failures to guarantee integrity, delivery and authorship of messages exchanged between processes. Its practical adoption strongly depends on the system assumptions. One of the most general (and hence versatile) such hypothesis assumes a set of processes interconnected through an unknown communication network of reliable and authenticated links, and an upper bound on the number of Byzantine faulty processes that may be present in the system, known to all participants. To this date, implementing a reliable communication service in such an environment may be expensive, both in terms of message complexity and computational complexity, unless the topology of the network is known. The target of this work is to combine the Byzantine fault-tolerant topology reconstruction with a reliable communication primitive, aiming to boost the efficiency of the reliable communication service component after an initial (expensive) phase where the topology is partially reconstructed. We characterize the sets of assumptions that make our objective achievable, and we propose a solution that, after an initialization phase, guarantees reliable communication with optimal message complexity and optimal delivery complexity.
2020
Symposium on Stabilization, Safety, and Security of Distributed Systems
Reliable communication; Byzantine fault tolerance; topology reconstruction
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Boosting the efficiency of Byzantine-tolerant reliable communication / Bonomi, Silvia; Farina, Giovanni; Tixeuil, Sébastien. - 12514:(2020), pp. 29-44. (Intervento presentato al convegno Symposium on Stabilization, Safety, and Security of Distributed Systems tenutosi a Austin, TX, USA) [10.1007/978-3-030-64348-5_3].
File allegati a questo prodotto
File Dimensione Formato  
Bonomi_postprint_Boosting_2020.pdf

accesso aperto

Note: https://link.springer.com/chapter/10.1007/978-3-030-64348-5_3
Tipologia: Documento in Post-print (versione successiva alla peer review e accettata per la pubblicazione)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 387.36 kB
Formato Adobe PDF
387.36 kB Adobe PDF
Bonomi_Boosting_2020.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 309.5 kB
Formato Adobe PDF
309.5 kB Adobe PDF   Contatta l'autore

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1462998
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
social impact